/***尚硅谷Java数据结构与java算法                 ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***桶排序         P73                         ***/
/***C++ 实现版本    written by Daniel           ***/

#include <iostream>
//用于获取系统时间
#include <ctime>
//用于生成随机数
#include <cstdlib>
#include <cstring>
#include <cmath>
using std::cout;
using std::endl;
//最大的缺陷是内存使用严重，很有可能导致内存不够用
//每次调用使用的内存数  为现有数组大小的10倍
#define MAX 80000000

void printArr(int *arr, int size)
{
    for (int i = 0; i < size; i++)
    {
        std::cout << arr[i] << "\t";
    }
    std::cout << std::endl;
}
/*
    桶排序属于空间换取时间的算法
*/

void radixSort(int *arr, const int size)
{
    //声明一个二位数组，二维数组的每个每一行代表一个桶
    //每个桶的最大空间为数组大小
    int(*bucket)[10] = new int[size][10];
    //声明一个数组，每个数组代表桶中有效数据的个数
    int *indexArr = new int[10];
    memset(indexArr, 0, 10);
    //将所有的数据循环放入桶中
    //i代表第 几轮 桶排序  
    int max=arr[0];
    //找出矩阵中的最大值，用于确定桶排序遍历的次数
    for(int i=0;i<size;i++){
        if (arr[i]>max){
            max=arr[i];
        }
    }
    //求解桶排序迭代的次数
    int itetorNum=0;
    while(max>0){
        max/=10;
        itetorNum++;
    }


    //代码中还缺少一个结束循环的判断 
    for (int i = 1;i<=itetorNum; i++)
    {
        for (int j = 0; j < size; j++)
        {
            //获取其个位数字，这个也是桶的编号
            int bucketNum = arr[j] % (static_cast<int>(pow(10,i)))/(static_cast<int>((pow(10,i-1))));
            //cout<<bucketNum<<endl;
            bucket[indexArr[bucketNum]][bucketNum] = arr[j];
            indexArr[bucketNum] += 1;
        }
        //将数据取出，放回到数组中
        int index = 0;
        for (int k = 0; k < 10; k++)
        {
            if (indexArr[k] > 0)
            {
                for (int l = 0; l < indexArr[k]; l++)
                {
                    arr[index] = bucket[l][k];
                    index++;
                }
            }
            indexArr[k]=0;
        }
    }

    // printArr(arr,size);
    if (bucket != nullptr)
    {
        delete[] bucket;
        bucket = nullptr;
    }
}

int main(int argc, char **argv)
{
    //使用系统时间生成一个随机数种子
    srand(time(NULL));
    int *array = new int[MAX];
    for (int i = 0; i < MAX; i++)
    {
        array[i] = rand() % MAX;
        // cout<<array[i]<<endl;
    }
    //printArr(array, MAX);
    time_t now = time(NULL);
    std::cout << "now=" << now << std::endl;
    radixSort(array, MAX);
    time_t newNow = time(NULL);
    //printArr(array, MAX);
    std::cout << "newNow=" << newNow << std::endl;
    std::cout << "一共花了" << newNow - now << "秒" << endl;
    delete[] array;
    return 0;
}